package algorithm.t202111;

import java.util.Arrays;
import java.util.HashSet;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/11/6 9:10
 * @description :5道
 * 昨夜下了雨，今天一天都是大风小雨，一天之间温度降的很多，手脚冻得冰凉，也临近入冬，也是大学/学生生涯最后一个冬季。
 * persevere to last
 * 2021.11.06
 * 李红磊
 * 2021年11月6日21:16:04
 */
public class t20211106 {

    //268.丢失的数字
    public int missingNumber(int[] nums) {
        HashSet<Integer> hashSet = new HashSet<>();

        Arrays.stream(nums).forEach(s -> hashSet.add(s));

        for (int i = 0; i <= nums.length; i++) {
            if (!hashSet.contains(i)) {
                return i;
            }
        }
        return -1;
    }

    public int missingNumber2(int[] nums) {

        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i != nums[i]) {
                return i;
            }
        }

        return nums.length;

    }

    //5.最长回文子串
    public String longestPalindrome(String s) {

        if (s.length() < 2) {
            return s;
        }

        int max_len = 1, len = s.length(), begin = 0;
        for (int i = 0; i < len - 1; i++) {

            for (int j = i + 1; j < len; j++) {

                if (j - i + 1 > max_len && isSon(i, j, s)) {
                    begin = i;
                    max_len = j - i + 1;
                }
            }

        }

        return s.substring(begin, max_len + begin);
    }//暴力解法，超时

    private boolean isSon(int i, int j, String str) {
        while (i < j) {
            if (str.charAt(i) != str.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }

    //中心扩散
    public String longestPalindrome2(String s) {
        if (s.length() < 2 || s == null) {
            return s;
        }

        int begin = 0, max_len = 1, len = s.length();

        for (int i = 0; i < len - 1; i++) {
            /*
                如 aba这个回文串，就是一个奇数，中间一个b
                如 accd这个就是一个偶数，中间是cc
             */
            int oddLen = expandAroundCenter(s, i, i);//以奇数为中心
            int evenLen = expandAroundCenter(s, i, i + 1);//以偶数

            int cur_len = Math.max(oddLen, evenLen);
            if (cur_len > max_len) {
                max_len = cur_len;
                begin = i - (max_len - 1) / 2;//难点
            }


        }
        return s.substring(begin, begin + max_len);

    }

    /**
     * @return int 此左右边界形成的回文子串的长度
     * @Author 李红磊
     * @Date 2021/11/6 11:50
     * @param: 目标字符串
     * @param: left 左边界
     * @param: right 右边界
     **/
    private int expandAroundCenter(String s, int left, int right) {
        int len = s.length();
        int l = left, r = right;
        while (l >= 0 && r < len) {
            if (s.charAt(l) == s.charAt(r)) {
                r++;
                l--;
            } else {
                break;
            }
        }
        return r - l - 1;
    }

    //413.等差数列划分
    public int numberOfArithmeticSlices(int[] nums) {
        if (nums.length < 3 || nums == null) return 0;

        int index = 1, len = nums.length, count = 0;

        for (int i = index; i < len - 1; i++) {

            if (nums[i + 1] - nums[i] == nums[i] - nums[i - 1]) {
                count++;
                int temp = i + 2;
                while (temp < len) {
                    if (nums[temp] - nums[temp - 1] == nums[i] - nums[i - 1]) {
                        count++;
                        temp++;
                    } else {
                        break;
                    }
                }
            }

        }

        return count;
    }

    //面试题16.05 阶乘尾数
    public int trailingZeroes(int n) {
        /**
         解题思路：
         1、那么 n 过大时，从 1 遍历到 n, 那么会超时,因此我们修改下规律

         n! = 1 * 2 * 3 * 4 * (1 * 5) * ... * (2 * 5) * ... * (3 * 5) ...
         我们发现，
         每隔 5 个数就会出现 一个 5，因此我们只需要通过 n / 5 来计算存在存在多少个 5 个数，那么就对应的存在多少个 5
         但是，我们也会发现
         每隔 25 个数会出现 一个 25， 而 25 存在 两个 5，我们上面只计算了 25 的一个 5，因此我们需要 n / 25 来计算存在多少个 25，加上它遗漏的 5
         同时，我们还会发现
         每隔 125 个数会出现一个 125，而 125 存在 三个 5，我们上面只计算了 125 的两个 5，因此我们需要 n / 125 来计算存在多少个 125，加上它遗漏的 5
         ...

         因此我们 count = n / 5 + n / 25 + n / 125 + ...
         最终分母可能过大溢出，上面的式子可以进行转换

         count = n / 5 + n / 5 / 5 + n / 5 / 5 / 5 + ...
         因此，我们这样进行循环
         n /= 5;
         count += n;
         这样，第一次加上的就是 每隔 5 个数的 5 的个数，第二次加上的就是 每隔 25 个数的 5 的个数 ...
         */

        int count = 0;
        while (n >= 5) {
            n /= 5;
            count += n;
        }
        return count;

    }

    //面试题16.06 最小差
    public int smallestDifference(int[] a, int[] b) {
        if (a.length == 1 && b.length == 1) {
            return Math.abs(a[0] - b[0]);
        }

        Arrays.sort(a);
        Arrays.sort(b);
        long res = Integer.MAX_VALUE;

        for (int i = 0, j = 0; i < a.length && j < b.length; ) {
            res = Math.min(res, Math.abs((long) a[i] - (long) b[j]));

            if (a[i] < b[j]) {
                i++;
            } else {
                j++;
            }

        }

        return (int) res;
    }

    public static void main(String[] args) {
        t20211106 t20211106 = new t20211106();
        System.out.println(t20211106.smallestDifference(new int[]{-2147483648, 1}, new int[]{2147483647, 0}));


    }


}
